Search for: All records

The paper introduces DiSProD, an online planner developed forenvironments with probabilistic transitions in continuous state andaction spaces. DiSProD builds a symbolic graph that captures thedistribution of future trajectories, conditioned on a given policy,using independence assumptions and approximate propagation ofdistributions. The symbolic graph provides a differentiablerepresentation of the policy's value, enabling efficient gradient-basedoptimization for long-horizon search. The propagation of approximatedistributions can be seen as an aggregation of many trajectories, makingit well-suited for dealing with sparse rewards and stochasticenvironments. An extensive experimental evaluation compares DiSProD tostate-of-the-art planners in discrete-time planning and real-timecontrol of robotic systems. The proposed method improves over existingplanners in handling stochastic environments, sensitivity to searchdepth, sparsity of rewards, and large action spaces. Additionalreal-world experiments demonstrate that DiSProD can control groundvehicles and surface vessels to successfully navigate around obstacles.

Although security games have attracted intensive research attention over the past years, few existing works consider how information from local communities would affect the game. In this paper, we introduce a new player -- a strategic informant, who can observe and report upcoming attacks -- to the defender-attacker security game setting. Characterized by a private type, the informant has his utility structure that leads to his strategic behaviors. We model the game as a 3-player extensive-form game and propose a novel solution concept of Strong Stackelberg-perfect Bayesian equilibrium. To compute the optimal defender strategy, we first show that although the informant can have infinitely many types in general, the optimal defense plan can only include a finite (exponential) number of different patrol strategies. We then prove that there exists a defense plan with only a linear number of patrol strategies that achieve the optimal defender's utility, which significantly reduces the computational burden and allows us to solve the game in polynomial time using linear programming. Finally, we conduct extensive experiments to show the effect of the strategic informant and demonstrate the effectiveness of our algorithm.